/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Chango
 */
public class Hoffman {

        public Node first, last;
	public Node treeRoot;
	public byte table[][];
	public String codeList[];
	private int size;
	private int count;

        public Hoffman(Node First){
            size=0;
            count=0;
        }

        public void addElement(Node newNode){
            if(first==null){
                first=newNode;
                last=newNode;
            }
            else{
                    Node aux =first;
                    while(aux.getRight()!=null)
                        aux=aux.getRight();
                    aux.setRight(newNode);
                    newNode.setLeft(aux);
                    last=newNode;
                }
            size++;
        }
        public void sort(){
            //ordena los nodos por de acuerdo a su frecuencia de menor a mayor
            Node aux1=first;
            Node aux2=aux1;
            int freqTemp;
            char charTemp;

            while(aux1!=null){
                while(aux2.getRight()!=null){
                    if(aux2.getFrequency()>=aux2.getRight().getFrequency()){
                        freqTemp=aux2.getFrequency();
                        charTemp=aux2.getCharacter();
                        aux2.setFrequency(aux2.getRight().getFrequency());
                        aux2.setCharacter(aux2.getRight().getCharacter());
                        aux2.getRight().setFrequency(freqTemp);
                        aux2.getRight().setCharacter(charTemp);

                        if(aux2.getCharacter()>aux2.getRight().getCharacter()&&aux2.getFrequency()==aux2.getRight().getFrequency()){
                            freqTemp=aux2.getFrequency();
                            charTemp=aux2.getCharacter();
                            aux2.setFrequency(aux2.getRight().getFrequency());
                            aux2.setCharacter(aux2.getRight().getCharacter());
                            aux2.getRight().setFrequency(freqTemp);
                            aux2.getRight().setCharacter(charTemp);
                        }
                    }
                    aux2=aux2.getRight();
                }
                aux2=first;
                aux1=aux1.getRight();
            }
        }

        public void createTree(){
         //crea el arbol huffman para la compresion
            Node aux=first,temp;
            table = new byte[size][3];
            codeList=new String[size];
            int weight =0;

            while(aux.getRight()!=null){
                if(aux.getRight()!=null){
                    weight=aux.getFrequency()+aux.getRight().getFrequency();
                }
                else
                    weight=aux.getFrequency();
            }
            temp = new Node((char)0,weight,false);
            temp=situateNode(temp,aux);
            temp.setLeftSon(aux);
            temp.setLeftSon(aux.getRight());
            aux=aux.getRight().getRight();

            if(aux.getRight()==null){
                treeRoot=temp;
            }
            createCode(treeRoot, "");
        }

        public Node situateNode(Node newNode, Node aux2){
            //ubica un nodo por medio de su frecuencia y byte
            Node aux=aux2;
            while(aux!=null){
                if(newNode.getFrequency()<=aux.getFrequency()){
                    aux.getLeft().setRight(newNode);
                    newNode.setLeft(aux.getLeft());
                    aux.setLeft(newNode);
                    newNode.setRight(aux);
                    return newNode;
                }
                if(aux.getRight()==null){
                    aux.setRight(newNode);
                    newNode.setLeft(aux);
                    last=newNode;
                    break;
                }
                aux=aux.getRight();
            }
            return newNode;
        }

        public void createCode(Node newNode, String str){
            /*genera codigo hoffman para todos los nodos dentro del arbol hoffman
              solo los nodos padres son excluidos*/
            if(newNode!=null){
                if(newNode.isTipe()){
                    newNode.setCode(str);
                    table[count][0]=(byte)newNode.getCharacter();
                    table[count][1]=(byte)newNode.getFrequency();
                    codeList[count]=str;
                    count++;
                }
                createCode(newNode.getLeftSon(), str+"0");
                createCode(newNode.getRightSon(),str+"1");
            }
        }

        public String getCode(byte value){
            //obtiene el codigo hoffman de un byte en especifico
            for(int i=0;i<size;i++)
                if(table[i][0]==value)
                    return codeList[i];
            return null;
        }

        public byte[][] getTable(){
            //tabla de frecuencias
            return table;
        }
        public int getSize(){
            //numero de nodos en la lista
            return size;
        }
}
